package solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-10-07 11:25
 */
public class Solution_6DP_greedy {
    /*===========================================================================================================================
     *DP 贪心 区间 435. 无重叠区间
     * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
     * 贪心选择：每次选择可选择区间中结束时间最早的区间
     *  */
    public int eraseOverlapIntervals(int[][] intervals) {
        int n=intervals.length;
        if (n==0) return 0;
        //按照结束时间升序排列
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int end=intervals[0][1];
        int res=1;
        for (int[] i:intervals) {
            int i_start=i[0];
            if (i_start>=end){
                //找到下一个不重叠区间
                res++;
                end=i[1];
            }
        }
        return n-res;
    }
    /*===========================================================================================================================
     *DP 贪心 区间 452. 用最少数量的箭引爆气球
     * 本质是一个区间选择问题，有多少不重叠的区间，就需要最少多少只箭
     *  */
    public int findMinArrowShots(int[][] points) {
        int n=points.length;
        if (n==0) return 0;
        //按照结束时间升序排列
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1]>o2[1]) return 1;
                else if (o1[1]<o2[1]) return -1;
                else return 0;
            }
        });
        int end=points[0][1];
        int res=1;
        for (int[] i:points) {
            int i_start=i[0];
            if (i_start>end){
                //找到下一个不重叠区间
                res++;
                end=i[1];
            }
        }
        return res;
    }
    /*===========================================================================================================================
     *DP 贪心 区间 253 会议室2
     * 给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。
     * 如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间
     * 首先把这些会议的时间区间进行投影：红色的点代表每个会议的开始时间点，绿色的点代表每个会议的结束时间点。
     * 现在假想有一条带着计数器的线，在时间线上从左至右进行扫描，每遇到红色的点，计数器 `count` 加一，
     * 每遇到绿色的点，计数器 `count` 减一，这样一来，每个时刻有多少个会议在同时进行，
     * 就是计数器 `count` 的值，`count` 的最大值，就是需要申请的会议室数量。
     *  */
    int minMeetingRooms(int[][] meetings){
        int n=meetings.length;
        int[] strat=new int[n];
        int[] end=new int[n];
        for (int i = 0; i < n; i++) {
            strat[i]=meetings[i][0];
            end[i]=meetings[i][1];
        }
        Arrays.sort(strat);
        Arrays.sort(end);
        int i=0,j=0;
        int count=0;
        int res=0;
        while (i<n&&j<n){
            if (strat[i]<end[j]){
                //扫描到一个开始
                count++;
                i++;
            } else{
                //扫描到一个结束
                count--;
                j++;
            }
            res=Math.max(res,count);
        }
        return res;
    }


    /*===========================================================================================================================
     *DP 贪心 区间 1024. 视频拼接
     * 你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
     * 我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
     * 思路：这个问题需要将这些视频片段（区间）按开始时间（左端点）排序，如果起点相同的话按照终点降序排序。
     * 这样我们就可以确定，如果 `clips[0]` 是的起点是 0，那么 `clips[0]` 这个视频一定会被选择。
     * 当我们确定 `clips[0]` 一定会被选择之后，就可以选出下一个会被选择的视频：
     * 我们会比较所有起点小于 `clips[0][1]` 的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频。
     * 总时间复杂度是 O(NlogN)
     *  */
    public int videoStitching(int[][] clips, int time) {
        int n=clips.length;
        Arrays.sort(clips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]==o2[0]){
                    return o2[1]-o1[1];
                }else {
                    return o1[0]-o2[0];
                }
            }
        });
        int index=0,curEnd=0,nextEnd=0;
        int res=0;
        while (index<n&&clips[index][0]<=curEnd){
            //在res个区间选定后开始选择下一个
            while (index<n&&clips[index][0]<=curEnd){
                nextEnd=Math.max(nextEnd,clips[index][1]);
                index++;//在选择下一个时，一定是从开始时间在当前区间结束时间之前的开始找
            }
            res++;
            // 找到下一个视频，更新 curEnd
            curEnd=nextEnd;
            if (curEnd>=time){
                return res;
            }
        }
        return -1;
    }



    /*===========================================================================================================================
     *DP 贪心 区间 1288. 删除被覆盖区间
     * 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖
     * 思路：按照区间的起点进行升序排序，起点相同的安装终点降序排列
     * 排序之后，两个相邻区间可能有如下三种相对位置，1.覆盖，2.部分重合（两个区间可以合并，成一个大区间），3.完全不重合
     *
     *  */
    public int removeCoveredIntervals(int[][] intervals) {
        int n=intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]==o2[0]){
                    return o2[1]-o1[1];
                }else {
                    return o1[0]-o2[0];
                }
            }
        });
        // 记录合并区间的起点和终点
        int l=intervals[0][0],r=intervals[0][1];
        //记录覆盖区间个数
        int count=0;
        for (int i = 1; i < n; i++) {
            int[] interval=intervals[i];
            if (interval[0]>=l&&interval[1]<=r){
                //1.找到覆盖区间
                count++;
            }
            // 情况二，找到相交区间，合并
            if (interval[0]<r&&interval[1]>=r){
                r=interval[1];
            }
            // 情况三，完全不相交，更新起点和终点
            if (interval[1]>r){
                l=interval[0];
                r=interval[1];
            }
        }
        return n-count;
    }

    /*===========================================================================================================================
     *DP 贪心 区间 56. 合并区间
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     *选择按start排序。对于几个相交区间合并后的结果区间x，x.start一定是这些相交区间中start最小的，x.end一定是这些相交区间中end最大的。
     *  */
    public int[][] merge(int[][] intervals) {
        int n=intervals.length;
        LinkedList<int[]> mergeList=new LinkedList<>();
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0]==o2[0]){
                return o2[1]-o1[1];
            }else {
                return o1[0]-o2[0];
            }
        });
        mergeList.add(new int[]{intervals[0][0],intervals[0][1]});
        for (int i = 1; i < n; i++) {
            int[] last=mergeList.getLast();
            if (last[1]>=intervals[i][0]){
                //更新最后一个区间的end
                last[1]=Math.max(last[1],intervals[i][1]);
                mergeList.removeLast();
                mergeList.add(new int[]{last[0],last[1]});
            }else {
                mergeList.add(new int[]{intervals[i][0],intervals[i][1]});
            }
        }
        int ms=mergeList.size();
        int[][] res=new int[ms][2];
        for (int i = 0; i < ms; i++) {
            res[i]=mergeList.get(i);
        }
        return res;
    }


    /*===========================================================================================================================
     *DP 贪心 区间 986. 区间列表的交集
     * 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
     *返回这 两个区间列表的交集 。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间
     * 例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
     * 思路：用两个索引指针在A和B中游走，把交集找出来，如果(a1,a2)和(b1,b2)的交集区间是[c1,c2]，
     *                                            1.两个区间没有交集，b2 < a1 or a2 < b1
     *                                            2.两个区间有交集，那么c1=max(a1,b1)，c2=min(a2,b2)
     *          指针是否移动取决与a2，b2的大小关系
     *  */
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int n=firstList.length;
        int m=secondList.length;
        int i=0,j=0;
        LinkedList<int[]> list=new LinkedList<>();
        while (i<n&&j<m){
//            System.out.println("j="+j+",i="+i);
            int a1=firstList[i][0],a2=firstList[i][1];
            int b1=secondList[j][0],b2=secondList[j][1];
/*            System.out.println("a1="+a1+",a2="+a2);
            System.out.println("b1="+b1+",b2="+b2);*/
            if (b2>=a1&&a2>=b1){
                //i，j有交集
                list.add(new int[]{Math.max(a1,b1),Math.min(a2,b2)});
            }
            if (b2<a2) {
                j++;
//                System.out.println("j="+j);
            } else {
                i++;
//                System.out.println("i="+i);
            }
        }
        int ls =list.size();
        int[][] res=new int[ls][2];
        for (int k = 0; k < ls; k++) {
            res[k]=list.get(k);
        }
        return res;
    }

    /*===========================================================================================================================
     *DP与贪心的区别 55. 跳跃游戏
     *给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标
     * 思路：每一步都计算一下从当前位置最远能够跳到哪里，然后和一个全局最优的最远位置 farthest 做对比
     *  */
    public boolean canJump(int[] nums) {
        int n=nums.length;
        int farthest=0;
        for (int i = 0; i < n-1; i++) {
            farthest=Math.max(farthest,i+nums[i]);
            if (farthest<=i) return false;
        }
        return farthest>=n-1;
    }


    /*===========================================================================================================================
     *DP与贪心的区别 45. 跳跃游戏 II
     *给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
     *  */
    //1.dp+备忘录：定义：从索引 p 跳到最后一格，至少需要 dp(nums, p) 步
    int[] memo45;
    public int jump1(int[] nums) {
        int n=nums.length;
        memo45=new int[n];
        Arrays.fill(memo45,n);
        return dp(nums,0);
    }
    /*状态就是当前所站立的索引 p，选择就是可以跳出的步数。*/
    int dp(int[] nums,int p){
        int n=nums.length;
        //base case 就是当 p 超过最后一格时，不需要跳跃：
        if (p>=n-1) return 0;
        if (memo45[p]!=n) return memo45[p];
        //穷举可以选择的步数，1到steps
        int steps=nums[p];
        for (int i = 1; i <=steps ; i++) {
            int subRes=dp(nums,p+i);
            //子问题需要加上从当前位置跳到子问题位置这一步
            memo45[p]=Math.min(memo45[p],subRes+1);
        }
        return memo45[p];
    }

    //贪心：每一步都选择潜力最大的选择，即在可以跳到的位置中，选择值最大的，这样下一次选择的区间最大
    public int jump2(int[] nums) {
        int n=nums.length;
        int count=0;
        //end标记可以选择的跳跃步数i+1到i+nums[i]
        int farthest=0,end=0;
        for (int i = 0; i < n-1; i++) {
            farthest=Math.max(farthest,i+nums[i]);
            if (i==end){
                //遍历到达当期这一次选择的最后一个可选位置，必须进行下一次选择，跳跃步数加1
                count++;
                end=farthest;
            }
        }
        return count;
    }


    /*===========================================================================================================================
     *DP 贪心:134. 加油站
     * 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
     * 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
     *  */
    //1、图像思路：用一个环形数组记录gas[i] - cost[i] 作为经过站点 i 的油量变化值。有了这个环形数组，我们需要判断这个环形数组中是否能够找到一个起点 start，使得从这个起点开始的累加和一直大于等于 0。
    //从站点0开始对环形数组做前缀和，则起点最有可能是前缀和中的最小值点，因为如果把这个「最低点」作为起点，就是说将这个点作为坐标轴原点，就相当于把图像「最大限度」向上平移了。这样就最有可能是的每一步的累加和大于等于0
    //如果 sum(gas[...]) < sum(cost[...])，总油量小于总的消耗，那肯定是没办法环游所有站点的。
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int n=gas.length;
        int sum=0;
        int index=0;int minsum=0;
        for (int i = 0; i < n; i++) {
            sum+=(gas[i]-cost[i]);
            if (minsum>sum){
                // 经过第 i 个站点后，使 sum 到达新低
                // 所以站点 i + 1 就是最低点（起点）
                index=i+1;
                minsum=sum;
            }
        }
        // 总油量小于总的消耗，无解
        if (sum<0)return -1;

        return index==n? 0:index;
    }

    //2.贪心：如果选择站点 i 作为起点「恰好」无法走到站点 j，那么 i 和 j 中间的任意站点 k 都不可能作为起点。
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n=gas.length;
        int sum=0;
        for (int i = 0; i < n; i++) {
            sum += (gas[i] - cost[i]);
        }
        // 总油量小于总的消耗，无解
        if (sum<0)return -1;
        // tank记录油箱中的油量
        int index=0,tank=0;
        for (int i = 0; i < n; i++) {
            tank+=gas[i]-cost[i];
            if (tank<0){
                // 无法从 index 走到 i
                // 所以站点 i + 1 应该是起点
                tank=0;
                index=i+1;
            }
        }
        return index==n? 0:index;

    }

    public static void main(String[] args) {
        Solution_6DP_greedy obj=new Solution_6DP_greedy();
        int[][] nums=new int[][]{{0,2},{5,10},{13,23},{24,25}};
        int[][] nums1=new int[][]{{1,5},{8,12},{15,24},{25,26}};
        //System.out.println(obj.merge(nums));
        System.out.println(obj.intervalIntersection(nums,nums1));
    }
}
